package com.mlh.sort;

public class HillSort {
    public static void main(String[] args) {
        int[] arr = {53, 17, 78, 9, 45, 65, 87, 32, 345, 7, 67, 1, 1, 1, 1, 1, 1, 1, 45, 6, 7, 8, 5, 3, -3};
        method2(arr);
        for (int temp : arr) {
            System.out.println(temp);
        }
    }

    //method1和method1本质没有区别，两种不同的写法而已
    //基于for循环
    public static void method1(int[] arr) {
        int res;//目标的最终位置
        int temp;//存储目标值
        for (int d = arr.length / 2; d > 0; d /= 2) {//计算增量
            for (int i = d; i < arr.length; i++) {//d之前的元素相当于 插入排序的0 直接跳过 从1开始
                temp = arr[i];
                for (res = i; res >= d; res -= d) {//以步距为d 进行插入排序的比较
                    if (temp < arr[res - d]) {
                        arr[res] = arr[res - d];
                    } else {
                        break;
                    }
                }
                arr[res] = temp;
            }
        }
    }

    //基于while
    public static void method2(int[] arr) {
        if (arr.length < 2) {
            return;
        }
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int index = i, val = arr[i];//记录该数的下标和值
                while (index >= gap && val < arr[index - gap]) {
                    arr[index] = arr[index - gap];
                    index -= gap;
                }
                arr[index] = val;
            }
        }
    }

}
